By “transmission of a message and adjacent information through a communication channel” is meant any type or mode of communication of the adjacent information and of the message.
By “adjacent information” is meant a noise disturbing the communication channel, the noise being known during encoding. By “noise” is meant any information that may disturb the transmission of the message. For example, in the case of transmission of a watermarked image, the image constitutes a noise disturbing transmission of the watermarking.
By “surjective correcting code” is meant a correcting code in which each message is associated with q code words, q being an integer greater than or equal to 2.
Consider a Gaussian communication channel 1 (FIG. 1) over which a signal w of maximum power P is transmitted.
The communication channel is disturbed by a noise x modelled by a random variable following a Normal X˜N(0,Q) law, and by a noise z modelled by a random variable following a Normal Z˜N(0,N) law.
The capacity of channel 1, i.e. its maximum theoretical transmission efficiency, is equal to:
  C  =            1      2        ⁢          log      ⁡              [                  1          +                      P                          Q              +              N                                      ]            
The higher the emission power P, the larger the capacity C. Conversely, the sum Q+N reduces the capacity C.
The publication by M. H. M. Costa “Writing on dirty paper” (IEEE Trans. on Information Theory, 29(3): 439-441, May 1983) discloses that when the noise x is known at the time of encoding, i.e. during generation of the signal w, the capacity C no longer depends on the power Q. The capacity C therefore becomes equal to the capacity of a Gaussian channel disturbed by a single source of noise Z. Knowledge of the noise x therefore makes it possible to increase the capacity C. The known noise x is called adjacent information.
The publication by A. S. Cohen and A. Lapidoth “Generalized Writing on Dirty Paper” (2002) shows that this result can be extended to channels other than Gaussian.
Let M be a set of messages that can be transmitted. Let mj be the j-th message of the set M, j being an integer between 1 and the number of messages in the set M.
To approach the limit of capacity C, digital communication systems use correcting codes for encoding the message mj and for generating, from the encoded message mj, a signal w that is resistant to the disturbances of the sources of noise.
For conventional communication channels, i.e. for which the noise x is not known during encoding, for example a turbo code or a low-density code (Low Density Parity Check, LDPC), is used as the correcting code, both of which give good performance.
For a channel with adjacent information, i.e. when the noise x is known during encoding, the correcting code must be structured in a particular way.
In fact, the conventional correcting codes are based on a dictionary that associates a code word uj with each message mj (bijective dictionary). FIG. 2 shows an example of a conventional correcting code, for a set of messages M having four elements. The correcting code comprises four code words u1, u2, u3 and u4 associated respectively with four messages m1, m2, m3 and m4.
Assume that the message to be encoded is m1. The associated code word is u1. However, in the presence of adjacent information x of power Q that is too high, the maximum emission power P does not allow the robustness zone (hatched zone) of the code word u1 to be reached. In fact, as can be seen in FIG. 2, with w representing the signal to be transmitted, the point representing the signal received w+x, located at the end of the arrow F on the circle C, is outside of the hatched zone that corresponds to the robustness zone of the code word u1. There will therefore be a decoding error.
To solve this problem, surjective correcting codes called “Costa codes” are used. In these correcting codes, each message mj is associated with q code words, q being an integer greater than or equal to 2.
A message mj is then encoded by selecting the code word uj,i closest to the adjacent information x from the q possible code words for encoding mj, i being an integer between 1 and q.
By way of example, FIG. 3 shows an ideal Costa code, with q=4 and the set M having four messages m1 to m4. The message m1 is associated with the code words u1,1, u1,2, u1,3 and u1,4. Similarly, each message mj is associated with the code words uj,1, uj,2, uj,3 and uj,4. Regardless of the message mj to be encoded and regardless of the position of the adjacent information x, nearby there is a code word uj,i associated with the message mj.
There are currently two types of construction for surjective codes. The first type of construction is derived from the digital communications community. It uses quantization techniques for creating surjective codes, and associates a conventional correcting code with them. Such codes are described for example in the publication by G. Le Guelvouit “Tatouage robuste d'images par turbo TCQ” [Robust watermarking of images by turbo TCQ] (Traitement du Signal, Vol. 25, No. 6, April 2009), in the publication by B. Chen and G. W. Wornell “Quantization Index Modulation: A Class of Provably Good Methods for Digital Watermarking and Information Embedding” (IEEE Trans. on Information Theory, 1999) and in the publication by J. Chou, S. S. Pradhan, and K. Ramchandran “Turbo coded trellis-based constructions for data embedding: channel coding with side information” (In Proc. Conf. on Signals, Systems and Computers, Asilomar, Calif., November 2001).
The quantization permits simple association of several code words uj,i with each message mj. It is based on determination of a quantization interval, which corresponds to the distance between two code words uj,i associated with one and the same message mj.
For example, in the scalar case, if the quantization interval is defined as equal to 10, the values 0, 10, 20, 30, etc. are associated with the ‘0’ bit and the values 5, 15, 25, 35, etc. to the ‘1’ bit. For encoding the ‘1’ bit with an adjacent information of 22, the code word 25 is then used.
This approach allows results to be obtained close to the theoretical limits of capacity C. The drawback is that it offers no robustness for the scale factors. For example, if the communication channel undergoes an unexpected attenuation by a factor 8/10, the code word 25 will be transformed to 20, i.e. to a code word associated with the ‘0’ bit.
FIG. 4 illustrates the principle of quantization in 2 dimensions. The set M comprises four messages. The code is constructed by quantization of the 2D space. Each message mj is associated with the code words uj,1 to uj,q. The code words repeat indefinitely. In FIG. 4, for reasons of clarity, only four code words uj,i are shown for each message mj. Quantization ensures a regular distribution of the code words uj,i in space and therefore good performance.
To transmit a message mj, the communication system selects, from the code words uj,i associated with the message mj, the code word uj,i closest to the adjacent information x, in the Euclidean sense. In FIG. 4, it is the vector u1,1 that is closest. Then the communication system generates the signal w from the code word uj,i selected, using a technique for compensating, by anticipation, the addition of noise x during transmission through the channel.
FIG. 5 shows the signal received y, corresponding to the signal transmitted w, the communication channel 1 having undergone attenuation. The signal received y leaves the robustness zone (hatched zone) of the code word uj,i. There is therefore a decoding error.
The second type of construction is derived from the digital watermarking community. It is described for example in the publication by M. L. Miller, G. J. Doërr and I. J. Cox. “Dirty-paper trellis codes for watermarking”, in IEEE Int. Conf. on Image Processing, Rochester, N.Y., September 2002.
This type of construction uses a convolutional code and a Viterbi decoding algorithm. The Viterbi decoding algorithm is modified by adding multiple arcs between states, so that each state at time t is linked to all the states of time t+1. The path, i.e. the succession of arcs, selected is a function of the message mj to be encoded and of the adjacent information x. The arcs correspond to pseudo-random sequences, and the distance between these sequences and the adjacent information is their correlation.
The advantage of this technique is that it is not sensitive to attenuation, and more generally to scale factors, as all the correlations are influenced in the same way. The path of the trellis will therefore be the same in the case when the communication channel undergoes attenuation. The drawback is that this approach gives results that are a long way from the limit of capacity C, i.e. an error rate as a function of the P/N ratio of the high communication channel 1.
FIG. 6 shows a surjective code based on the Viterbi correlation and algorithm. The set M comprises four messages. The code words uj,i are arranged on a circle and therefore have the same energy. Consequently, the code is not sensitive to the change of scale. However, the code words uj,i are not distributed uniformly, which limits the performance.
Document XP010790760 Ourique et al., “Angle QIM: A novel watermark embedding scheme robust against amplitude scaling distortions,”2005 IEEE International Conference on Acoustics, Speech, and Signal Processing, 18-23 Mar. 2005, Philadelphia, PA, USA) describes a method of watermarking comprising the construction of a surjective correcting code based on characterization of the adjacent information in a spherical coordinate system. However, construction of the correcting code lacks precision.